package me.sealer.algorithm.dynamicprogramming;

import java.util.Scanner;

/**
 * @author sealer
 * @date 2018/02/23.
 * POJ1163
 * <p>
 * 输入格式：
 * 5      // 表示三角形的行数, 接下来输入三角形
 * 7
 * 3   8
 * 8   1   0
 * 2   7   4   4
 * 4   5   2   6   5
 * <p>
 * 在上面的数字三角形中寻找一条从顶部到底边的路径，使得
 * 路径上所经过的数字之和最大。路径上的每一步都只能往左
 * 下或 右下走。只需要求出这个最大和即可，不必给出具体路
 * 径。 三角形的行数大于1小于等于100，数字为 0 - 99
 */
public class MaxNumTriangle {

    private static int[][] maxNum = new int[5][5];
//    private static final int[][] TRIANGLE_ARRAY = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};

    /**
     * 递归实现 int sum = recursiveSolution(TRIANGLE_ARRAY, TRIANGLE_ARRAY.length, 0, 0);
     *
     * @param triangleArray
     * @param length        二维数组的行数
     * @param i             row 从0开始
     * @param j             column 从0开始
     * @return 坐标 triangleArray[i][j]距离最底端的最大路径之和
     */
    public static int recursiveSolution(int[][] triangleArray, int length, int i, int j) {
        if (length == i + 1) { // 若i, j位于最后一行， 则该节点到最后一行的最大路径之和即为本身节点数值大小。
            return triangleArray[i][j];
        }
        int leftMaxNum = recursiveSolution(triangleArray, length, i + 1, j);
        int rightMaxNum = recursiveSolution(triangleArray, length, i + 1, j + 1);
        int subMaxNum = Math.max(leftMaxNum, rightMaxNum);
//        System.out.println("triangleArray[" + i + "][" + j + "]: " + triangleArray[i][j] + "\t" + subMaxNum);
        return triangleArray[i][j] + subMaxNum; // 若该节点不为叶子节点(最后一行节点), 则最大路径之和为： (该节点数值大小+子节点的路径之和较大者)
    }

    /**
     * 记忆型递归实现 int sum = rememberRecursiveSolution(TRIANGLE_ARRAY, TRIANGLE_ARRAY.length, 0, 0);
     *
     * @param triangleArray
     * @param length        二维数组的行数
     * @param i             row 从0开始
     * @param j             column 从0开始
     * @return 坐标 triangleArray[i][j]距离最底端的最大路径之和
     */
    public static int rememberRecursiveSolution(int[][] triangleArray, int length, int i, int j) {
        if (length == i + 1) {
            maxNum[i][j] = triangleArray[i][j];
        } else {
            int leftMaxNum = recursiveSolution(triangleArray, length, i + 1, j);
            int rightMaxNum = recursiveSolution(triangleArray, length, i + 1, j + 1);
            maxNum[i][j] = triangleArray[i][j] + Math.max(leftMaxNum, rightMaxNum);
        }
        return maxNum[i][j];
    }

    /**
     * 二维数组动态规划实现 int sum = dpWithD2ArraySolution(TRIANGLE_ARRAY, TRIANGLE_ARRAY.length);
     *
     * @param triangleArray
     * @param length
     * @return
     */
    public static int dpWithD2ArraySolution(int[][] triangleArray, int length) {
        // 最后一行原样赋值 获取到最后一行的一维数组后取长度， 再遍历
        for (int j = 0; j < triangleArray[length - 1].length; j++) {
            // 最后一行原样赋值
            maxNum[length - 1][j] = triangleArray[length - 1][j];
        }

        // 从倒数第二行开始， 依次推理
        for (int i = length - 2; i >= 0; i--) {
            int columnNum = triangleArray[i].length;
            for (int j = 0; j < columnNum; j++) {
                int leftMaxNum = maxNum[i + 1][j];
                int rightMaxNum = maxNum[i + 1][j + 1];
                maxNum[i][j] = triangleArray[i][j] + Math.max(leftMaxNum, rightMaxNum);
            }
        }
        return maxNum[0][0];
    }

    /**
     * 一维数组动态规划实现 dpWithD1ArraySolution(TRIANGLE_ARRAY, TRIANGLE_ARRAY.length);
     *
     * @param triangleArray
     * @param length
     * @return
     */
    public static int dpWithD1ArraySolution(int[][] triangleArray, int length) {
        int[] maxNumber = triangleArray[length - 1]; // 这样可以节省一维数组空间

        for (int i = length - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                int leftMaxNum = maxNumber[j];
                int rightMaxNum = maxNumber[j + 1];
                maxNumber[j] = Math.max(leftMaxNum, rightMaxNum) + triangleArray[i][j];
            }
        }
        return maxNumber[0];
    }

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int lineCount = in.nextInt();
        int[][] triangleArray = new int[lineCount][lineCount];
        for (int i = 0; i < lineCount; i++) {
            for (int j = 0; j <= i; j++) {
                triangleArray[i][j] = in.nextInt();
            }
        }
//        long startTime = System.currentTimeMillis();
        int sum = dpWithD1ArraySolution(triangleArray, triangleArray.length);
//        long endTime = System.currentTimeMillis();
        System.out.println(sum);
    }
}


/*
demo input:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 */